#include "CellSpacePartition.h"
#include "GLPrimitives.h"
#include "General Utils.hpp"
#include "GameWorld.h"
#include "GLFT_Font.hpp"
#include "Pool.h"

CellSpacePartition::CellSpacePartition(double width,
										double height,
										int cellsX,
										int cellsY,
										int MaxEntities):
			m_dSpaceWidth(width),
			m_dSpaceHeight(height),
			m_iNumCellsX(cellsX),
			m_iNumCellsY(cellsY),
			m_Neighbors(MaxEntities)
{
	// calculate the bounds of each cell
	m_dCellSizeX = width / cellsX;
	m_dCellSizeY = height / cellsY;

	// create the cells
	for (int y = 0; y < m_iNumCellsY; ++y)
	{
		for(int x = 0; x < m_iNumCellsX; ++x)
		{
			double left = x * m_dCellSizeX;
			double right = left + m_dCellSizeX;
			double top = y * m_dCellSizeY;
			double bot = top + m_dCellSizeY;

			m_Cells.push_back(Cell(Vector2D(left, top), Vector2D(right, bot)));
		}
	}
}


//====================== Calculate Neighbors ============================
// 
// This must be called to create the vector of neighbors. This method
// examines each cell within the range of the target, If the cells contain entities
// then they are tested to see if they are situated within the target's neighborhood
// region. If they are, they are added to the neighbor list
//=======================================================================

void CellSpacePartition::CalculateNeighbors(Vector2D TargetPos, double QueryRadius)
{
	// create an iterator and set it to the beginning of the neighbor vector
	vector<BaseGameEntity*>::iterator curNbor = m_Neighbors.begin();

	// create the query box that is the boudning box of the target's query 
	// area (i.e. the circle with QueryRadius centered at TargetPos)

	Vector2D topleft = (TargetPos - Vector2D(QueryRadius, QueryRadius));
	Vector2D botright = (TargetPos + Vector2D(QueryRadius, QueryRadius));
	GameRectangle QueryBox = GetRect(topleft.x, topleft.y, botright.x, botright.y);

	int StartX = QueryBox.x / m_dCellSizeX;
	int StartY = QueryBox.y / m_dCellSizeY;

	int EndX = (QueryBox.x + QueryBox.width) / m_dCellSizeX;
	int EndY = (QueryBox.y + QueryBox.height) / m_dCellSizeY;


	for(int i = StartX; i <= EndX; i++)
		for(int j = StartY; j <= EndY; j++)
		{
			// test to see if this cell contains member and if it overlaps the 
			// query box
			if(i + j*m_iNumCellsY >= 0 && i + j*m_iNumCellsY < m_Cells.size()) // If it's in a safe range
			{
				if(Intersects(m_Cells[i + j*m_iNumCellsY].BBox, QueryBox) && !m_Cells[i + j*m_iNumCellsY].Members.empty())
				{
					list<BaseGameEntity*>::iterator it = m_Cells[i + j*m_iNumCellsY].Members.begin();
					for(it; it != m_Cells[i + j*m_iNumCellsY].Members.end(); ++it)
					{
						if (Vec2DDistanceSq((*it)->Pos(), TargetPos) < QueryRadius*QueryRadius)
						{
							*curNbor++ = *it;
						}
					}
				}
			}
			else
			{
				assert(0 && "OUT OF RANGE!");
			}
		}

	

	// mark the end of the list with a zero.
	
	*curNbor = 0; 
}

// ======================= CalculateCollisions =========================
// Identical to CalculateNeighbors but goes to the CRadius of the entities
void CellSpacePartition::CalculateCollisions(BaseGameEntity* anEntity)
{	
	// create an iterator and set it to the beginning of the neighbor vector
	vector<BaseGameEntity*>::iterator curNbor = m_Neighbors.begin();
	double QueryRadius = anEntity->CRadius();

	// create the query box that is the boudning box of the target's query 
	// area (i.e. the circle with QueryRadius centered at TargetPos)

	Vector2D topleft = (anEntity->Pos() - Vector2D(QueryRadius, QueryRadius));
	Vector2D botright = (anEntity->Pos() + Vector2D(QueryRadius, QueryRadius));
	GameRectangle QueryBox = GetRect(topleft.x, topleft.y, botright.x, botright.y);

	int StartX = QueryBox.x / m_dCellSizeX;
	int StartY = QueryBox.y / m_dCellSizeY;

	int EndX = (QueryBox.x + QueryBox.width) / m_dCellSizeX;
	int EndY = (QueryBox.y + QueryBox.height) / m_dCellSizeY;


	for(int i = StartX; i <= EndX; i++)
		for(int j = StartY; j <= EndY; j++)
		{
			// test to see if this cell contains member and if it overlaps the 
			// query box
			if(i + j*m_iNumCellsY >= 0 && i + j*m_iNumCellsY < m_Cells.size()) // If it's in a safe range
			{
				if(Intersects(m_Cells[i + j*m_iNumCellsY].BBox, QueryBox) && !m_Cells[i + j*m_iNumCellsY].Members.empty())
				{
					list<BaseGameEntity*>::iterator it = m_Cells[i + j*m_iNumCellsY].Members.begin();
					for(it; it != m_Cells[i + j*m_iNumCellsY].Members.end(); ++it)
					{
						if (Vec2DDistanceSq((*it)->Pos(), anEntity->Pos()) < QueryRadius*QueryRadius + (*it)->CRadius()*(*it)->CRadius())
						{
							*curNbor++ = *it;
						}
					}
				}
			}
			else
			{
				assert(0 && "OUT OF RANGE!");
			}
		}

	

	// mark the end of the list with a zero.
	
	*curNbor = 0; 
}

// ========================== CalculateOverlaps ==============================

void CellSpacePartition::CalculateOverlaps(Vector2D TargetPos, double QueryRadius)
{
		// create an iterator and set it to the beginning of the neighbor vector
	vector<BaseGameEntity*>::iterator curNbor = m_Neighbors.begin();

	// create the query box that is the boudning box of the target's query 
	// area (i.e. the circle with QueryRadius centered at TargetPos)

	Vector2D topleft = (TargetPos - Vector2D(QueryRadius, QueryRadius));
	Vector2D botright = (TargetPos + Vector2D(QueryRadius, QueryRadius));
	GameRectangle QueryBox = GetRect(topleft.x, topleft.y, botright.x, botright.y);

	int StartX = QueryBox.x / m_dCellSizeX;
	int StartY = QueryBox.y / m_dCellSizeY;

	int EndX = (QueryBox.x + QueryBox.width) / m_dCellSizeX;
	int EndY = (QueryBox.y + QueryBox.height) / m_dCellSizeY;


	for(int i = StartX; i <= EndX; i++)
		for(int j = StartY; j <= EndY; j++)
		{
			// test to see if this cell contains member and if it overlaps the 
			// query box
			if(i + j*m_iNumCellsY >= 0 && i + j*m_iNumCellsY < m_Cells.size()) // If it's in a safe range
			{
				if(Intersects(m_Cells[i + j*m_iNumCellsY].BBox, QueryBox) && !m_Cells[i + j*m_iNumCellsY].Members.empty())
				{
					list<BaseGameEntity*>::iterator it = m_Cells[i + j*m_iNumCellsY].Members.begin();
					for(it; it != m_Cells[i + j*m_iNumCellsY].Members.end(); ++it)
					{
						if (Vec2DDistanceSq((*it)->Pos(), TargetPos) < QueryRadius*QueryRadius + (*it)->BRadius()*(*it)->BRadius())
						{
							*curNbor++ = *it;
						}
					}
				}
			}
			else
			{
				assert(0 && "OUT OF RANGE!");
			}
		}

	

	// mark the end of the list with a zero.
	
	*curNbor = 0; 
}

void CellSpacePartition::CalculateOverlaps(BaseGameEntity* anEntity)
{	
	// create an iterator and set it to the beginning of the neighbor vector
	vector<BaseGameEntity*>::iterator curNbor = m_Neighbors.begin();
	double QueryRadius = anEntity->BRadius();

	// create the query box that is the boudning box of the target's query 
	// area (i.e. the circle with QueryRadius centered at TargetPos)

	Vector2D topleft = (anEntity->Pos() - Vector2D(QueryRadius, QueryRadius));
	Vector2D botright = (anEntity->Pos() + Vector2D(QueryRadius, QueryRadius));
	GameRectangle QueryBox = GetRect(topleft.x, topleft.y, botright.x, botright.y);

	int StartX = QueryBox.x / m_dCellSizeX;
	int StartY = QueryBox.y / m_dCellSizeY;

	int EndX = (QueryBox.x + QueryBox.width) / m_dCellSizeX;
	int EndY = (QueryBox.y + QueryBox.height) / m_dCellSizeY;


	for(int i = StartX; i <= EndX; i++)
		for(int j = StartY; j <= EndY; j++)
		{
			// test to see if this cell contains member and if it overlaps the 
			// query box
			if(i + j*m_iNumCellsY >= 0 && i + j*m_iNumCellsY < m_Cells.size()) // If it's in a safe range
			{
				if(Intersects(m_Cells[i + j*m_iNumCellsY].BBox, QueryBox) && !m_Cells[i + j*m_iNumCellsY].Members.empty())
				{
					list<BaseGameEntity*>::iterator it = m_Cells[i + j*m_iNumCellsY].Members.begin();
					for(it; it != m_Cells[i + j*m_iNumCellsY].Members.end(); ++it)
					{
						if (Vec2DDistanceSq((*it)->Pos(), anEntity->Pos()) < QueryRadius*QueryRadius + (*it)->BRadius()*(*it)->BRadius())
						{
							*curNbor++ = *it;
						}
					}
				}
			}
			else
			{
				assert(0 && "OUT OF RANGE!");
			}
		}

	

	// mark the end of the list with a zero.
	
	*curNbor = 0; 
}

//============================ Empty =============================
// 
// clears the cells of all entities
//================================================================

void CellSpacePartition::EmptyCells()
{
	std::vector<Cell>::iterator it = m_Cells.begin();
	for(it; it != m_Cells.end(); ++it)
	{
		it->Members.clear();
	}
}

//===================== PositionToIndex ================================
// 
// Given a 2D vector representing a position within the game world, this 
// method calculates an index into its appropriate cell
//=================================================================

int CellSpacePartition::PositionToIndex(const Vector2D& pos)const
{
  int idx = (int)(m_iNumCellsX * pos.x / m_dSpaceWidth) + 
            ((int)((m_iNumCellsY) * pos.y / m_dSpaceHeight) * m_iNumCellsX);

	// if the entity's position is equal to the vector2d(m_dSpaceWidth, m_dSpaceHeight)
	// then the index will overshoot, We need to check for this and adjust
	if (idx > (int)m_Cells.size()-1) idx = (int) m_Cells.size()-1;
	
	return idx;
}

// ========================== AddEntity =======================================
//
//  Used to add the entities to the data structure
// ===========================================================================

 void CellSpacePartition::AddEntity(BaseGameEntity* ent)
{
	int idx = PositionToIndex(ent->Pos());
	
	m_Cells[idx].Members.push_back(ent);
}

 // ====================== AddPool =============================
 // Used to add a pool to the data structure. 
 void CellSpacePartition::AddPool(Pool* pool)
 {
	 int idx = PositionToIndex(pool->Location());
	 m_Cells[idx].m_Pools.push_back(pool);
 }

 // ========================= UpdateEntity ===================================
// 
// Checks to see if an entity has moved cells. If so, the data structure is
// updated accordingly

void CellSpacePartition::UpdateEntity(BaseGameEntity* ent, Vector2D OldPos)
{
	// if the index for the old pos and the new pos are not equal then
	// the entity has moved to another cell.
	int OldIdx = PositionToIndex(OldPos);
	int NewIdx = PositionToIndex(ent->Pos());


	if(NewIdx == OldIdx) return;
	// the entity has moved into another cell so Delete from the current cell
	// and add to the new one
	m_Cells[OldIdx].Members.remove(ent);

	list<BaseGameEntity*>::iterator iter = m_Cells[NewIdx].Members.begin();
	bool entAlreadyInHere = false;

	for(iter; iter != m_Cells[NewIdx].Members.end(); iter++)
		if((*iter)->ID() == ent->ID())
			entAlreadyInHere = true;

	if(!entAlreadyInHere)
		m_Cells[NewIdx].Members.push_back(ent);
}

void CellSpacePartition::RenderCells()
{
	for(int i = 0; i < m_Cells.size(); i++)
	{
		if(ClipPlane->IsInPlane(m_Cells[i].BBox))
		{
			DrawPrimitives->DrawLine(m_Cells[i].BBox.x - ClipPlane->GetX(), m_Cells[i].BBox.y - ClipPlane->GetY(), m_Cells[i].BBox.x + m_Cells[i].BBox.width - ClipPlane->GetX(), m_Cells[i].BBox.y - ClipPlane->GetY(), white);
			DrawPrimitives->DrawLine(m_Cells[i].BBox.x - ClipPlane->GetX(), m_Cells[i].BBox.y - ClipPlane->GetY(), m_Cells[i].BBox.x - ClipPlane->GetX(), m_Cells[i].BBox.y + m_Cells[i].BBox.height - ClipPlane->GetY(), white);
			
			Vector2D TextLocation = Vector2D(m_Cells[i].BBox.x + 10, m_Cells[i].BBox.y + 10);
			for(list<BaseGameEntity*>::iterator iter = m_Cells[i].Members.begin(); iter != m_Cells[i].Members.end(); iter++)
			{
				char buffer[100];
				string message = itoa((*iter)->ID(), buffer, 10); 
				//TextDisplay->DisplayMessage(message, black, TextLocation.x - ClipPlane->GetX(), TextLocation.y -ClipPlane->GetY(), 20.0f);
				Key->GetFont("onuava")->drawText(TextLocation.x - ClipPlane->GetX(), TextLocation.y -ClipPlane->GetY(), message, black);

				TextLocation.y += 15;
				if(TextLocation.y > (m_Cells[i].BBox.y + m_Cells[i].BBox.height) - 40)
				{
					TextLocation.y = m_Cells[i].BBox.y + 10;
					TextLocation.x += 50;
				}
			}
				
		}
	}
}

bool CellSpacePartition::CollidesWithWater(Vector2D Pos, double radius)
{
	int idx = PositionToIndex(Pos);
	list<Pool*>::iterator CurPool = m_Cells[idx].m_Pools.begin();
	
	// Is the circumscribed rectangle
	GameRectangle TempRect(Pos.x - radius, Pos.y - radius, 2*radius, 2*radius);

	while(CurPool != m_Cells[idx].m_Pools.end())
	{
		if((*CurPool)->IntersectsPool(TempRect))
			return true;

		CurPool++;
	}

	return false;
}